package com.lry.sort;

import java.util.Arrays;

/**
 * @author JiangJie
 * @create 2020-12-18 16:23
 */
public class QuickSort {
    //2 3 5 4 1
    //1 3 5 4 2
    //1 2 5 4 3

    public static void main(String[] args) {
        int[]arr= new int[]{2,3,5,4,1};
        new QuickSort().sort(arr);
        Arrays.stream(arr).forEach(System.out::println);
    }
    public void sort(int[] arr){
        sort(arr,0,arr.length-1);
    }
    public void sort(int[] arr,int i,int j){
        if(i<j){
            int par = partition(arr,i,j);
            sort(arr,i,par-1);
            sort(arr,par+1,j);
        }
    }

    public int partition(int[] arr,int i,int j){
        while(i<j){

            while(i<j&&arr[i]<=arr[j]){
                j--;
            }
            if(arr[i]>arr[j]){
                swap(arr,i,j);
                i++;
            }

            while(i<j&&arr[i]<=arr[j]){
                i++;
            }
            if(arr[i]>arr[j]){
                swap(arr,i,j);
                j--;
            }
        }
        return i;
    }

    public void swap(int[]arr,int i,int j){
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

}
